package com.sheng.leetcode.year2025.month10.day16;

import org.junit.Test;

/**
 * @author by ls
 * @date 2025/10/17
 * <p>
 * 2598. 执行操作后的最大 MEX<p>
 * <p>
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。<p>
 * 在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。<p>
 * 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。<p>
 * 数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。<p>
 * 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。<p>
 * 返回在执行上述操作 任意次 后，nums 的最大 MEX 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,-10,7,13,6,8], value = 5<p>
 * 输出：4<p>
 * 解释：执行下述操作可以得到这一结果：<p>
 * - nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]<p>
 * - nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]<p>
 * - nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]<p>
 * nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [1,-10,7,13,6,8], value = 7<p>
 * 输出：2<p>
 * 解释：执行下述操作可以得到这一结果：<p>
 * - nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]<p>
 * nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length, value <= 10^5<p>
 * -10^9 <= nums[i] <= 10^9<p>
 */
public class LeetCode2598 {

    @Test
    public void test() {
        int[] nums = {1, -10, 7, 13, 6, 8};
//        int value = 5;
        int value = 7;
        System.out.println(new Solution().findSmallestInteger(nums, value));
    }
}

class Solution {

    public int findSmallestInteger(int[] nums, int value) {
        // 统计数组 nums 中每个元素和 value 余数的出现次数
        int[] count = new int[value];
        for (int num : nums) {
            // 计算余数，处理负数情况，获取正余数
            int remainder = (num % value + value) % value;
            count[remainder]++;
        }

        // 贪心查找 MEX
        int mex = 0;
        while (true) {
            // 从 0 开始计算余数，如果余数出现次数大于 0，则表示该余数可以被使用，mex 加 1，否则跳出循环
            int remainder = mex % value;
            if (count[remainder] > 0) {
                count[remainder]--;
                mex++;
            } else {
                break;
            }
        }
        return mex;
    }

// 超时
//    public int findSmallestInteger(int[] nums, int value) {
//        // 数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。
//        // 返回在执行上述操作 任意次 后，nums 的最大 MEX 。
//        int n = nums.length;
//        if (value == 1) {
//            return nums.length;
//        }
//        // 标识数组内的元素是否已被使用
//        boolean[] flag = new boolean[n];
//        // 大概操作就是从 0 开始，依次递增判断数组内的元素，再进行增减 value之后，是否能满足
//        for (int i = 0; i < n; i++) {
//            boolean is = true;
//            for (int j = 0; j < n; j++) {
//                if (!flag[j]) {
//                    if ((i - nums[j]) % value == 0) {
//                        flag[j] = true;
//                        is = false;
//                        nums[j] = i;
//                        break;
//                    }
//                }
//            }
//            if (is) {
//                return i;
//            }
//        }
//        return nums.length;
//    }
}
